//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
// 
//
// 示例 3： 
//
// 
//输入：nums1 = [0,0], nums2 = [0,0]
//输出：0.00000
// 
//
// 示例 4： 
//
// 
//输入：nums1 = [], nums2 = [1]
//输出：1.00000
// 
//
// 示例 5： 
//
// 
//输入：nums1 = [2], nums2 = []
//输出：2.00000
// 
//
// 
//
// 提示： 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -106 <= nums1[i], nums2[i] <= 106 
// 
//
// 
//
// 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？ 
// Related Topics 数组 二分查找 分治 
// 👍 4206 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int k = ( nums1.length + nums2.length + 1) >> 1;
        int midA,midB;
        //是找前k个的一个特例
        //如果是奇数，找到第k个
        System.out.println("nums1:"+Arrays.toString(nums1));
        System.out.println("nums2:"+Arrays.toString(nums2));

        midA = findK(nums1,nums2,0,0,k,0);
        if((nums1.length + nums2.length) % 2 == 1){
            return midA * 1.0;
        }
        //如果是偶数，找到第k个及k+1个取平均值
        midB = findK(nums1,nums2,0,0,k+1,0);
        return (midA + midB)/2.0;
    }
    public int findK(int[] nums1, int[] nums2,int nums1From,int nums2From, int k,int deep){

//        if(deep >= 10){
//            return 0;
//        }
        System.out.println("nums1From:"+nums1From+",nums2From:"+nums2From+",k:"+k);

        //如果一个数组没有元素可遍历了，那么直接从另外一个数组取出剩余的即可，k - 1 是因为k代表数量
        if(nums1From == nums1.length) return nums2[nums2From + k - 1];
        if(nums2From == nums2.length) return nums1[nums1From + k - 1];
        //如果只剩一个需要比较了
        if(k == 1) return Math.min(nums1[nums1From],nums2[nums2From]);

        int nums1Counts,nums2Counts;
        nums1Counts = Math.min( k/2,nums1.length - nums1From);//别超限
        nums2Counts = Math.min( k - nums1Counts, nums2.length - nums2From);//别超限
        nums1Counts = k - nums2Counts;//别不够
        System.out.println("nums1Count:"+nums1Counts+", num2Counts:"+nums2Counts);
        //比较两个数组中k/2位置的大小
        //小的那一个数组，前k/2可以排除掉，因为不可能有第k个数（最多可以排到k-1个）

        //之所以需要 nums1Counts - 1 ,是因为，nums1Counts代表有多少个元素，比如一个元素，它就是1，但是转化成索引，就是0
        if(nums1[nums1From + nums1Counts - 1] <= nums2[nums2From + nums2Counts - 1]){
            //nums1from+nums1Counts 不用-1，是因为 包含 [nums1From + nums1Counts - 1] 及以前的元素都不要了
            //k-nums1Counts 不用-1，是因为k与nums1Counts都代表数量
            return findK(nums1,nums2,nums1From+nums1Counts,nums2From,k-nums1Counts,deep+1);
        }else{
            return findK(nums1,nums2,nums1From,nums2From+nums2Counts,k-nums2Counts,deep+1);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
